package com.yayako.struc;

import com.yayako.utils.FileUtil;

import java.util.*;

/**
 * 预测分析表
 *
 * @author cyy
 */
public class M {
    private static final String EPSILON = "ε";
    private static final String POUND_KEY = "#";
    private static final String SET_OUTPUT_PATH =
            "D:\\Projects\\Fundamentals of Compiling\\SyntacticParser\\src\\com\\yayako\\out\\m";
    private static final String TABLE_OUTPUT_PATH =
            "D:\\Projects\\Fundamentals of Compiling\\SyntacticParser\\src\\com\\yayako\\out\\table_m";
    private String S;
    private CFG cfg;
    private TreeMap<String, TreeSet<String>> first;
    private TreeMap<String, TreeSet<String>> follow;
    private TreeMap<String, TreeMap<String, CFG.Production>> M;
    private StringBuilder logger;

    public M(CFG cfg) {
        this.cfg = cfg;
        this.S = cfg.getS();
        this.logger = new StringBuilder();
        creFirst();
        creFollow();
        creM();
        write2Txt();
    }

    /** 构建FIRST集合 */
    private void creFirst() {
        first = new TreeMap<>();
        String key;
        for (Map.Entry<String, List<CFG.Production>> entry : cfg.getP().entrySet()) {
            key = entry.getKey();
            first.put(key, creFirst(key, entry.getValue()));
        }
    }

    private TreeSet<String> creFirst(String key, List<CFG.Production> productions) {
        TreeSet<String> first = this.first.get(key);
        if (first != null) {
            return first;
        }
        TreeSet<String> T = cfg.getT();
        first = new TreeSet<>();
        String firstSymbol;
        for (CFG.Production production : productions) {
            firstSymbol = production.getFirst();
            // 终结符，直接加入first集
            if (T.contains(firstSymbol)) {
                first.add(firstSymbol);
            } else {
                // 非终结符，递归创建first
                first.addAll(creFirst(firstSymbol, cfg.getP().get(firstSymbol)));
            }
        }
        return first;
    }

    /** 构建FOLLOW集合（全篇第二鸡肋代码） */
    private void creFollow() {
        follow = new TreeMap<>();
        // 开始符号
        TreeSet<String> S = new TreeSet<>();
        S.add(POUND_KEY);
        follow.put(cfg.getS(), S);
        follow.put(cfg.getS(), creFollow(cfg.getS()));
        for (String s : cfg.getN()) {
            if (!s.equals(cfg.getS())) {
                follow.put(s, creFollow(s));
            }
        }
    }

    private TreeSet<String> creFollow(String key) {
        TreeSet<String> follow = this.follow.get(key);
        if (follow != null && !key.equals(cfg.getS())) {
            return follow;
        }
        if (!key.equals(cfg.getS())) {
            follow = new TreeSet<>();
        }
        // 遍历非终结符
        for (Map.Entry<String, List<CFG.Production>> entry : cfg.getP().entrySet()) {
            List<CFG.Production> right = entry.getValue();
            // 遍历产生式列表
            getFollow(key, right, follow);
        }
        return follow;
    }

    private void getFollow(String key, List<CFG.Production> right, TreeSet<String> follow) {
        TreeSet<String> N = cfg.getN();
        String next; // β
        for (CFG.Production production : right) {

            if (production.getRight().contains(key)) {
                int n = production.getRight().size();
                // 遍历产生式
                for (int i = 0; i < n; ++i) {
                    String s = production.getRight().get(i);
                    if (s.equals(key)) {
                        // A -> αBβ
                        if (i + 1 < n) {
                            // FIRST(β)
                            next = production.getRight().get(i + 1);
                            // β为非终结符
                            if (N.contains(next)) {
                                TreeSet<String> tmp = new TreeSet<>(first.get(next));
                                // 存在 "ε"
                                if (tmp.remove(EPSILON) && !production.getLeft().equals(key)) {
                                    // FOLLOW(A)
                                    tmp.addAll(
                                            this.follow.getOrDefault(
                                                    production.getLeft(),
                                                    creFollow(production.getLeft())));
                                }
                                follow.addAll(tmp);
                            } else {
                                // β为终结符，直接加入
                                follow.add(next);
                            }
                        }
                        // A -> αB
                        else {
                            if (!production.getLeft().equals(key)) {
                                // FOLLOW(A)
                                follow.addAll(
                                        this.follow.getOrDefault(
                                                production.getLeft(),
                                                creFollow(production.getLeft())));
                            }
                        }
                        ++i;
                    }
                }
            }
        }
    }

    /** 构建预测分析表 */
    private void creM() {
        M = new TreeMap<>();
        TreeMap<String, CFG.Production> map;
        // 遍历非终结符
        for (Map.Entry<String, List<CFG.Production>> entry : cfg.getP().entrySet()) {
            String key = entry.getKey();
            List<CFG.Production> productions = entry.getValue();
            map = new TreeMap<>();

            // 遍历产生式列表
            for (CFG.Production production : productions) {
                // FIRST(α)
                TreeSet<String> first = this.first.get(production.getFirst());
                if (first == null && !EPSILON.equals(production.getFirst())) {
                    // 终结符
                    map.put(production.getFirst(), production);
                } else if (first == null && EPSILON.equals(production.getFirst())) {
                    // "ε"
                    TreeSet<String> follow = this.follow.get(key);
                    for (String s : follow) {
                        map.put(s, production);
                    }
                } else if (first != null) {
                    // 遍历FIRST集合，对FIRST(α)的每个终结符a，加入α到M[A，a]
                    for (String s : first) {
                        map.put(s, production);
                    }
                    // 若ε∈FIRST(α)，则FOLLOW(A)每个终结符b（包括#），加入α到M[A，b]
                    if (first.contains(EPSILON)) {
                        TreeSet<String> follow = this.follow.get(key);
                        for (String s : follow) {
                            map.put(s, production);
                        }
                    }
                }
            }
            M.put(key, map);
        }
    }

    private boolean checkAmbiguity(TreeMap<String, CFG.Production> map, String s) {
        if (map.containsKey(s)) {
            logger.append("二义性文法！请检查！");
            FileUtil.write2Log(logger.toString());
            return true;
        }
        return false;
    }

    private void write2Txt() {
        FileUtil.write2Txt(SET_OUTPUT_PATH, writeSet(), false);
        FileUtil.write2Txt(TABLE_OUTPUT_PATH, writeTable(), false);
    }

    private String writeTable() {
        StringBuilder stringBuilder = new StringBuilder();
        for (String s : cfg.getT()) {
            if (EPSILON.equals(s)) {
                continue;
            }
            stringBuilder.append('\t').append(s);
        }
        stringBuilder.append('\t').append(POUND_KEY);
        for (String s : M.keySet()) {
            stringBuilder.append('\n').append(s);
            TreeMap<String, CFG.Production> map = M.get(s);
            for (String t : cfg.getT()) {
                if (EPSILON.equals(t)) {
                    continue;
                }
                CFG.Production tmp = map.get(t);
                if (tmp == null) {
                    stringBuilder.append("\t ");
                } else {
                    stringBuilder.append('\t').append(tmp.getProduction());
                }
            }

            // for #
            CFG.Production tmp = map.get(POUND_KEY);
            if (tmp == null) {
                stringBuilder.append("\t ");
            } else {
                stringBuilder.append('\t').append(tmp.getProduction());
            }
        }
        return stringBuilder.toString();
    }

    private String writeSet() {
        StringBuilder firstBuilder = new StringBuilder("FIRST:\n");
        StringBuilder followBuilder = new StringBuilder("\nFOLLOW:\n");
        StringJoiner firstJoiner, followJoiner;
        for (String s : first.keySet()) {
            firstBuilder.append("\tFIRST(").append(s).append(")\t=\t");
            followBuilder.append("\tFOLLOW(").append(s).append(")\t=\t");
            firstJoiner = new StringJoiner(" ", "{ ", " }");
            followJoiner = new StringJoiner(" ", "{ ", " }");
            for (String f : first.get(s)) {
                firstJoiner.add(f);
            }
            for (String f : follow.get(s)) {
                followJoiner.add(f);
            }
            firstBuilder.append(firstJoiner.toString()).append('\n');
            followBuilder.append(followJoiner.toString()).append('\n');
        }
        firstBuilder.append(followBuilder);
        return firstBuilder.toString();
    }

    public String getS() {
        return S;
    }

    public CFG getCfg() {
        return cfg;
    }

    public TreeMap<String, TreeMap<String, CFG.Production>> getM() {
        return M;
    }
}
